package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-20
 * Time:14:39
 */

/**
 * 力扣面试经典150:79. 单词搜索
 * 中等
 * 相关标签
 * 相关企业
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * 示例 1：
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 */
public class exist {
    public static void main(String[] args) {
        char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        System.out.println(exist(board, "ABCCED"));
    }
    static int m;
    static int n;
    static boolean[][] visited;

    public static boolean exist(char[][] board, String word) {
        n = board.length;
        m = board[0].length;
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private static boolean dfs(char[][] board, String word, int row, int col, int index) {
        // 已经找到完整的单词
        if (index == word.length()) {
            return true;
        }

        // 越界、已访问过、字符不匹配的情况
        if (row < 0 || row >= n || col < 0 || col >= m || visited[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        }

        //将当前访问的字符标记为已使用，以避免重复使用同一个单元格的字符。在递归结束后，需要将该字符恢复为未使用状态
        visited[row][col] = true; // 标记当前单元格为已访问

        //上下左右寻址
        boolean exists = dfs(board, word, row + 1, col, index + 1) ||
                         dfs(board, word, row - 1, col, index + 1) ||
                         dfs(board, word, row, col + 1, index + 1) ||
                         dfs(board, word, row, col - 1, index + 1);

        visited[row][col] = false; // 恢复当前单元格为未访问

        return exists;
    }

}
